#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/23 10:41
# ===========================================
#       题目名称： 29. 两数相除
#       题目地址： https://leetcode.cn/problems/divide-two-integers/description/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    def divide(self, dividend, divisor):
        """
            效率低下
        """
        MAX_VALUE = pow(2, 31) - 1
        MIN_VALUE = pow(-2, 31)
        if divisor == 0:
            return 0
        if dividend == MAX_VALUE:
            if divisor == -1:
                return MIN_VALUE + 1
            if divisor == 1:
                return MAX_VALUE
        if dividend == MIN_VALUE:
            if divisor == -1:
                return MAX_VALUE
            if divisor == 1:
                return MIN_VALUE
        count = 0
        temp_dividend = abs(dividend)  # 求绝对值
        temp_divisor = abs(divisor)
        const_16 = temp_divisor << 16
        const_10 = temp_divisor << 10
        const_8 = temp_divisor << 8
        const_5 = temp_divisor << 5
        const_2 = temp_divisor << 2
        while temp_dividend >= temp_divisor:
            if temp_dividend >= const_16:
                temp_dividend -= const_16
                count += 65536
            if temp_dividend >= const_10:
                temp_dividend -= const_10
                count += 1024
            if temp_dividend >= const_8:
                temp_dividend -= const_8
                count += 256
            if temp_dividend >= const_5:
                temp_dividend -= const_5
                count += 32
            if temp_dividend >= const_2:
                temp_dividend -= const_2
                count += 4
            if temp_dividend >= temp_divisor:
                temp_dividend -= temp_divisor
                count += 1
        if not ((dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)):
            count = - count
        return count


if __name__ == '__main__':
    s = Solution()
    # 3
    print(s.divide(dividend=10, divisor=3))
    # -2
    print(s.divide(dividend=7, divisor=-3))
    # 1
    print(s.divide(dividend=1, divisor=1))
    # 1
    print(s.divide(dividend=-1, divisor=-1))
    # 1073741823
    print(s.divide(dividend=2147483647, divisor=2))
    # -2147483647
    print(s.divide(dividend=2147483647, divisor=-1))
    # 2147483647
    print(s.divide(dividend=-2147483648, divisor=-1))
